package leetcode.D200.T188;

import java.util.Arrays;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-22 15:36:48 星期二
 */

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length <= 1)
            return 0;
        int[] dp0 = new int[k+1], dp1 = new int[k+1];
        Arrays.fill(dp1, -prices[0]);
        for (int i = 1; i < prices.length; i++) {
            int last = dp0[0];
            for(int j= 1; j <= k; ++j) {
                int temp = dp0[j];
                dp0[j] = Math.max(dp0[j], dp1[j]+prices[i]);
                dp1[j] = Math.max(dp1[j], last-prices[i]);
                last = temp;
            }
        }
        int result = 0;
        for(int i=0; i<dp0.length; ++i) {
            result = Math.max(result, dp0[i]);
        }
        return result;
    }
}
